﻿#include <iostream>
#include <cmath>
using namespace std;

//爱吃素（数学）
//https://ac.nowcoder.com/acm/problem/227310

//bool isprime(long long n)
//{
//	if (n <= 1)
//		return false;
//	for (int i = 2; i <= sqrt(n); i++)
//	{
//		if (n % i == 0)
//			return false;
//	}
//	return true;
//}
//
//int main()
//{
//	int t;
//	cin >> t;
//	while (t--)
//	{
//		long long a, b;
//		cin >> a >> b;
//		if ((a == 1 && isprime(b)) || (b == 1 && isprime(a)))
//			cout << "YES" << endl;
//		else
//			cout << "NO" << endl;
//	}
//}


//相差不超过k的最多数（滑动窗⼝）
//https://www.nowcoder.com/practice/562630ca90ac40ce89443c91060574c6?tpId=308&tqId=40490&ru=/exam/oj

//#include<algorithm>
//
//const int N = 2e5 + 5;
//int arr[N];
//
//int main() {
//    int n, k;
//    cin >> n >> k;
//    for (int i = 0; i < n; i++) cin >> arr[i];
//    sort(arr, arr + n);
//
//    int left = 0, right = 0, ret = 0;
//    while (right < n)
//    {
//        while (arr[right] - arr[left]>k)
//            left++;
//        ret = max(ret, right - left + 1);
//        right++;
//    }
//    cout << ret;
//}


//最⻓公共⼦序列(⼀)（动态规划 - LCS）
//file:///D:/Code/written-exam-training/%E8%AF%BE%E4%BB%B6/%E7%AC%94%E8%AF%95%E5%BC%BA%E8%AE%AD%E7%AC%AC%2005%20%E5%91%A8.pdf

//DP N^2复杂度 适合数据量较小时

//dp[i][j]表示：字符串 s1 中 [0, i] 区间与字符串 s2 中 [0, j] 区间内所有的⼦序列中，
//最⻓公共⼦序列的⻓度是多少。
//状态转移⽅程：根据最后⼀个位置的字符情况，划分问题：
//a.s1[i] == s2[j]：dp[i][j] = dp[i - 1][j - 1] + 1；
//b.s1[i] != s2[j]：dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])。

//const int N = 1010;
//char s1[N];
//char s2[N];
//int dp[N][N];
//
//int main()
//{
//	int n, m;
//	cin >> n >> m;
//	for (int i = 1; i <= n; i++) 
//		cin >> s1[i];
//	for (int i = 1; i <= m; i++) 
//		cin >> s2[i];
//
//	for (int i = 1; i <= n; i++)
//	{
//		for (int j = 1; j <= m; j++)
//		{
//			if (s1[i] == s2[j])
//				dp[i][j] = dp[i - 1][j - 1] + 1;
//			else
//				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
//		}
//	}
//	cout << dp[n][m] << endl;;
//}

//贪心+二分 N*logN

//对于所有子序列，只要知道每个长度为x的序列的末尾是什么
//存长度为x的序列，只存末尾最小的那个
//优化：二分查找插入位置

//class Solution {
//    int dp[100010] = { 0 };//dp[i]:表示长度为i的最小末尾
//    int pos = 0;
//public:
//    int LIS(vector<int>& a) {
//        for (auto x : a)
//        {
//            if (pos == 0 || x > dp[pos])
//                dp[++pos] = x;
//            else
//            {
//                int l = 1, r = pos;
//                while (l < r)
//                {
//                    int mid = (l + r) / 2;
//                    if (dp[mid] >= x)
//                        r = mid;
//                    else
//                        l = mid + 1;
//                }
//                dp[l] = x;
//            }
//        }
//        return pos;
//    }
//};


